Despite its long history, the classical game of peg solitaire continues to attract the attention of the scientific community. In this paper, we consider two problems with an algorithmic flavour which are related with this game, namely Solitaire-Reachability and Solitaire-Army. In the first one, we show that deciding whether there is a sequence of jumps which allows a given initial configuration of pegs to reach a target position is NP-complete. Regarding Solitaire-Army, the aim is to successfully deploy an army of pegs in a given region of the board in order to reach a target position. By solving an auxiliary problem with relaxed constraints, we are able to answer some open questions raised by Csakany and Juhasz (Mathematics Magazine, 2000). © Luciano Gualà and Stefano Leucci and Emanuele Natale, and Roberto Tauraso.
Large Peg-Army Maneuvers / Gualà, Luciano; Leucci, Stefano; Natale, Emanuele; Tauraso, Roberto. - ELETTRONICO. - 49:(2016). (Intervento presentato al convegno 8th International Conference on Fun with Algorithms, FUN 2016 tenutosi a La Maddalena; Italy) [10.4230/LIPIcs.FUN.2016.18].
Large Peg-Army Maneuvers
LEUCCI, STEFANO;NATALE, EMANUELE;
2016
Abstract
Despite its long history, the classical game of peg solitaire continues to attract the attention of the scientific community. In this paper, we consider two problems with an algorithmic flavour which are related with this game, namely Solitaire-Reachability and Solitaire-Army. In the first one, we show that deciding whether there is a sequence of jumps which allows a given initial configuration of pegs to reach a target position is NP-complete. Regarding Solitaire-Army, the aim is to successfully deploy an army of pegs in a given region of the board in order to reach a target position. By solving an auxiliary problem with relaxed constraints, we are able to answer some open questions raised by Csakany and Juhasz (Mathematics Magazine, 2000). © Luciano Gualà and Stefano Leucci and Emanuele Natale, and Roberto Tauraso.| File | Dimensione | Formato | |
|---|---|---|---|
|
Guala_Large_2016.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
672.78 kB
Formato
Adobe PDF
|
672.78 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
